1. Field of the Invention
The present invention relates to encoding devices and methods for performing serially concatenated convolutional coding or serial concatenated trellis coded modulation and to decoding devices and methods for decoding codes generated by serially concatenated convolutional coding or serial concatenated trellis coded modulation performed by such encoding devices and methods.
2. Description of the Related Art
Nowadays, a considerable amount of research is being conducted in communications fields, such as mobile communications and deep space communications, and in broadcasting fields, such as terrestrial and satellite digital broadcasting. In relation to such research, coding theory research has been extensively conducted to improve the efficiency of error-correcting coding and decoding.
One known theoretical limit of code performance is the Shannon limit, which is given by Shannon""s channel coding theorem.
The purpose of coding theory research is to develop codes that have near-Shannon-limit performance. Recently, for example, serially concatenated convolutional codes (hereinafter referred to as SCCC) have been developed by an encoding method that generates codes showing performance near the Shannon limit.
SCCC coding is performed by serially concatenating two convolutional encoders and an interleaver. SCCC decoding is performed by serially concatenating two soft-output decoder circuits, which exchange information with each other to obtain a final decoded result.
One known application of SCCC coding is serial concatenated trellis coded modulation (hereinafter referred to as SCTCM), which is described in D. Divsalar and F. Pollara, xe2x80x9cSerial and Hybrid Concatenation Codes with Applicationsxe2x80x9d, in Proc. Int. Symp. on Turbo Codes and Related Topics, Brest, France, pp. 80-87, September 1997. SCTCM combines SCCC coding and multi-level modulation and takes into consideration the entirety of the signal constellation of modulated signals and the decoding characteristics of error-correcting codes.
Specific examples of an encoding device that performs SCTCM coding and a decoding device that performs decoding of a code in SCTCM will now be described. In the following description, as shown in FIG. 13, digital information is encoded by an encoding device 201 included in a transmitter (not shown). The output of the encoder 201 is input to a receiver (not shown) via a memoryless channel 202 and decoded by a decoding device 203 included in the receiver. The decoded information is then observed.
The encoding device 201 that performs SCTCM coding includes, for example, as shown in FIG. 14, a convolutional encoder 210 that encodes an outer code, an interleaver 220 that permutes input data, a convolutional encoder 230 that encodes an inner code, and a multi-level modulation mapping circuit 240 that performs signal point mapping based on a predetermined modulation system. The encoding device 201 performs a serially concatenated convolutional operation on 2-bit input data D201 with a code rate of 2/3 to convert the input data D201 into 3-bit encoded data D204, maps the encoded data D204 to a transmission symbol in, for example, eight-phase shift keying (hereinafter referred to as 8PSK), and outputs a resultant 3-bit encoded transmission symbol D205.
Referring to FIG. 15, the convolutional encoder 210 has three exclusive OR circuits 211, 213, and 215 and two shift registers 212 and 214.
The exclusive OR circuit 211 computes the exclusive OR of 2-bit input data D2011 and D2022 and supplies the computation result to the shift register 212.
The shift register 212 continuously supplies 1-bit data maintained therein to the exclusive OR circuit 213. In synchronization with a clock signal, the shift register 212 maintains new 1-bit data supplied from the exclusive OR circuit 211 and supplies the new data to the exclusive OR circuit 213.
The exclusive OR circuit 213 computes the exclusive OR of data supplied from the shift register 212 and the 1-bit input data D2011 of the 2-bit input data D201 and supplies the computation result to the shift register 214.
The shift register 214 continuously supplies 1-bit data maintained therein to the exclusive OR circuit 215. In synchronization with a clock signal, the shift register 214 maintains new 1-bit data supplied from the exclusive OR circuit 213 and supplies the new data to the exclusive OR circuit 215.
The exclusive OR circuit 215 computes the exclusive OR of data supplied from the shift register 214 and the input data D2011 and D2012 and supplies the computation result serving as 1-bit encoded data D2023 of 3-bit encoded data D202 to the interleaver 220 at a subsequent stage.
When the convolutional encoder 210 described above receives the 2-bit input data D2011 and D2022, the convolutional encoder 210 performs a convolutional operation of the input data D2011 and D2022 and outputs the operation result as 3-bit encoded data D2021, D2022, and D2023 to the interleaver 220 at the subsequent stage. In other words, the convolutional encoder 210 performs a convolutional operation to encode the outer code with a code rate of 2/3 and outputs the generated encoded data D202 to the interleaver 220 at the subsequent stage.
The interleaver 220 interleaves the encoded data D202 consisting of a 3-bit sequence output from the convolutional encoder 210 and outputs interleaved data D203 consisting of the generated 3-bit sequence to the convolutional encoder 230 at a subsequent stage.
Referring to FIG. 16, the convolutional encoder 230 includes an exclusive OR circuit 231 and a shift register 232.
The exclusive OR circuit .231 computes the exclusive OR of 3-bit interleaved data D2031, D2032, and D2033. The exclusive OR circuit 231 outputs the computation result serving as 1-bit encoded data D2043 of 3-bit encoded data D204 to the multi-level modulation mapping circuit 240 at a subsequent stage and supplies the computation result to the shift register 232.
The shift register 232 continuously supplies 1-bit data maintained therein to the exclusive OR circuit 231. In synchronization with a clock signal, the shift register 232 maintains new 1-bit data supplied from the exclusive OR circuit 231 and supplies the new data to the exclusive OR circuit 231.
When the convolutional encoder 230 described above receives the 3-bit interleaved data D2031, D2032, and D2033, the convolutional encoder 210 performs a convolutional operation of the interleaved data D2031, D2032, and D2033 and outputs the operation result as 3-bit encoded data D2041, D2042, and D2043 to the multi-level modulation mapping circuit 240 at the subsequent stage. In other words, the convolutional encoder 230 performs a convolutional operation to encode the inner code with a code rate of 3/3=1 and outputs the generated encoded data D204 to the multi-level modulation mapping circuit 240 at the subsequent stage.
In synchronization with a clock signal, the multi-level modulation mapping circuit 240 maps the encoded data D204 output from the convolutional encoder 230 to, for example, an 8PSK transmission symbol. Specifically, the multi-level modulation mapping circuit 240 maps the 3-bit encoded data D204 output from the convolutional encoder 230 as a single transmission symbol and generates a single encoded transmission symbol D205. The multi-level modulation mapping circuit 240 outputs the generated encoded transmission symbol D205 to the outside.
In the encoding device 201 described above, the convolutional encoder 210 performs a convolutional operation to encode the outer code with a code rate of 2/3 and the convolutional encoder 230 performs a convolutional operation to encode the inner code with a code rate of 1, resulting in performing a serially concatenated convolutional operation with an overall code rate of (2/3)xc3x971=2/3. The data encoded and modulated by the encoding device 201 is output to the receiver via the memoryless channel 202.
In contrast, the decoding device 203 that decodes a code in SCTCM generated by the encoding device 201 includes, for example, as shown in FIG. 17, a soft-output decoder circuit 250 that decodes the inner code, a de-interleaver 260 that rearranges the order of input data to the original order, and a soft-output decoder circuit 280 that decodes the outer code. The decoding device 203 estimates the input data D201 of the encoding device 201 from a received value D206, which is an analog value due to the effects of noise generated on the memoryless channel 202 and which serves as soft-input, and outputs the estimated data as decoded data D211.
The soft-output decoder circuit 250 is associated with the convolutional encoder 230 of the encoding device 201. The soft-output decoder circuit 250 performs maximum a-posteriori probability (hereinafter referred to as MAP) decoding based on the BCJR algorithm described in Bahl, Cocke, Jelinek, and Raviv, xe2x80x9cOptimal Decoding of Linear Codes for Minimizing Symbol Error Ratexe2x80x9d, IEEE Trans. Info. Theory, Vol. IT-20, pp. 284-287, March 1974 or based on the Max-Log-MAP algorithm or the Log-MAP algorithm that is an improvement of the BCJR algorithm and that is described in Robertson, Villebrun, and Hoeher, xe2x80x9cA Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domainxe2x80x9d, IEEE Int. Conf. on Communications, pp. 1009-1013, June 1995 (hereinafter referred to as the Max-Log-BCJR algorithm or the Log-BCJR algorithm) or soft-output Viterbi algorithm (SOVA) decoding. The soft-output decoder circuit 250 receives the soft-input received value D206 received by the receiver and soft-input a-priori probability information D207 that is supplied from the interleaver 270 and that corresponds to information bits and performs soft-output decoding of the inner code using the received value D206 and the a-priori probability information D207. The soft-output decoder circuit 250 generates extrinsic information D208 that corresponds to information bits and that is obtained in accordance with the code""s constraint condition and outputs the extrinsic information D208 serving as soft-output to the de-interleaver 260 at a subsequent stage. The extrinsic information D208 corresponds to the interleaved data D203 that has been interleaved by the interleaver 220 of the encoding device 201.
The de-interleaver 260 de-interleaves the soft-input extrinsic information D208 output from the soft-output decoder circuit 250 so as to rearrange the bit sequence of the interleaved data D203 that has been interleaved by the interleaver 220 of the encoding device 201 to the bit sequence of the original encoded data D202. The de-interleaver 260 outputs the de-interleaved data serving as a-priori probability information D209 corresponding to encoded bits to the soft-output decoder circuit 280 at a subsequent stage.
The interleaver 270 interleaves soft-input extrinsic information D210 that is output from the soft-output decoder circuit 280 and that corresponds to encoded bits on the basis of the same rearrangement position information as that of the interleaver 220 of the encoding device 201. The interleaver 270 outputs the interleaved data serving as the a-priori probability information D207 corresponding to the information bits to the soft-output decoder circuit 250.
The soft-output decoder circuit 280 is associated with the convolutional encoder 210 of the encoding device 201. As in the case with the soft-output decoder circuit 250, the soft-output decoder circuit 280 performs MAP decoding based on the above-described BCJR algorithm, Max-Log-BCJR algorithm, or Log-BCJR algorithm or SOVA decoding. The soft-output decoder circuit 280 receives the soft-input a-priori probability information D209 that is output from the de-interleaver 260 and that corresponds to the encoded bits and a-priori probability information (not shown) that has a value of zero and that corresponds to information bits and performs soft-output decoding of the outer code using these pieces of a-priori probability information. The soft-output decoder circuit 280 generates the extrinsic information D210 that corresponds to the encoded bits and that is obtained in accordance with the code""s constraint condition and outputs the extrinsic information D210, serving as soft-output, to the interleaver 270. The soft-output decoder circuit 280 also generates so-called a-posteriori probability information (not shown) that corresponds to information bits and that is obtained in accordance with the code""s constraint condition and outputs hard-output decoded data D211 on the basis of the a-posteriori probability information.
When the decoding device 203 described above receives the received value D206, the decoding device 203 iterates the decoding operation involving the circuits from the soft-output decoder circuit 250 to the soft-output decoder circuit 280 a predetermined number of times, such as a few times to several dozen times, and outputs the decoded data D211 on the basis of the soft-output extrinsic information obtained as a result of the decoding operation performed the predetermined number of times.
One criterion for code design is referred to as the maximum likelihood (ML) criterion. A performance curve for representing the code performance is drawn in terms of the relationship between the bit error rate represented logarithmically (log10BER) and the signal-to-noise power ratio per bit (Eb/No). The performance curve has a bit error rate at which a so-called error floor occurs, that is, the bit error rate cannot be reduced any further by increasing the signal-to-noise power ratio. The ML criterion is a criterion for reducing the bit error rate at which the error-floor occurs, that is, a criterion for optimizing the weight distribution of the overall code.
The error floor is known to be determined by a code""s distance structure. Specifically, a term that dominates the bit error rate at which an error floor occurs in a code with block length N is represented by expression (1) where df0 denotes the minimum distance of the outer code. When the outer code""s minimum distance df0 is an even number, xcex42 is expressed by equation (2) where dfxc2x7eff denotes the minimum effective Euclidean distance of the inner code. When the outer code""s minimum distance df0 is an odd number, xcex42 is expressed by equation (3) where hm(3) denotes the minimum Euclidean distance with respect to an input Hamming distance of three.
Nxe2x88x92└(df0+1)/2┘exe2x88x92xcex42(Eb/4No)xe2x80x83xe2x80x83(1)
where └x┘ denotes the integer portion of real number x.                               δ          2                =                                            d              f              0                        ⁢                          d              feff              2                                2                                    (        2        )                                          δ          2                =                                                            (                                                      d                    f                    0                                    -                  3                                )                            ⁢                              d                feff                2                                      2                    +                                    (                              h                m                                  (                  3                  )                                            )                        2                                              (        3        )            
The term that dominates the bit error rate at which the error floor occurs in the code having block length N depends on the inner code""s Euclidean distance with respect to an input distance of two when the outer code""s minimum distance df0 is an even number, and it depends on the inner code""s Euclidean distance with respect to input distances of two and three when the outer code""s minimum distance df0 is an odd number. In code design, maximizing the Euclidean distance is a condition for achieving a low error rate.
In order to perform code design in view of the ML criterion for reducing the bit error rate at which such an error floor occurs, the following five steps should be taken.
In code design, first, the so-called set partitioning technique or the like is used to optimize the distribution of output distances, thus creating a trellis that is not catastrophic.
Subsequently, in code design, the output distance with respect to an input Hamming distance of one is set to infinity in order not to generate many codewords with a low output distance. In other words, in code design, for example, such a path that branches off at a state on a trellis with an input Hamming distance of one, reaches another state, and returns to the original state with an input Hamming distance of zero is eliminated. As a result, the trellis does not terminate with an input Hamming distance of one. In the case of a code following such a path, even if an interleaver is provided, when the outer code""s distance is small, the outer code is interspersed by the interleaver into the input code. Due to the fact that every bit sequence generates a small output distance, many termination patterns are generated, resulting in a high error floor.
Code design thus observes the ML criterion. Specifically, in code design, the inner code""s output distance with respect to an input distance of two is maximized. When the outer code""s minimum distance df0 is an odd number, the inner code""s output distance with respect to an input distance of three is maximized. In code design, when a code is constructed in accordance with the ML criterion, the code""s weight distribution is optimized. As a result, the error floor is reduced.
Subsequently, in code design, input and output positions are mapped onto the trellis so as to satisfy both conditions, that is, the condition that the trellis does not terminate with an input Hamming distance of one and the condition that the ML criterion is observed.
In code design, the output of an encoder is set to the positions of signal points so that the output can be represented in terms of a convolution code.
In code design, the above-described steps are taken to design a code with a low error floor.
A specific example of SCTCM code design by taking these steps is described in D. Divsalar, S Dolinar, and F. Pollara, xe2x80x9cSerial Concatenated Trellis Coded Modulation with Rate-1 Inner Codexe2x80x9d, GLOBECOM 2000, which will now be described.
In this paper, a convolutional encoder 300 shown in FIG. 18 is used as a convolutional encoder that encodes the inner code. Specifically, the convolutional encoder 300 includes three exclusive OR circuits 301, 302, and 303 and a shift register 304.
The exclusive OR circuit 301 computes the exclusive OR of data supplied from the shift register 304 and input interleaved data D3011 and supplies the computation result as 1-bit encoded data D3021 of 3-bit encoded data D302 to a multi-level modulation mapping circuit (not shown) at a subsequent stage.
The exclusive OR circuit 302 computes the exclusive OR of the input interleaved data D3011 and D3012 and outputs the computation result as 1-bit encoded data D3022 of the 3-bit encoded data D302 to the multi-level modulation mapping circuit at the subsequent stage.
The exclusive OR circuit 303 computes the exclusive OR of data supplied from the shift register 304 and the input interleaved data D3011, D3012, and D3013. The exclusive OR circuit 303 supplies the computation result to the shift register 304 and outputs the computation result as 1-bit encoded data D3023 of the 3-bit encoded data D302 to the multi-level modulation mapping circuit at the subsequent stage.
The shift register 304 continuously supplies 1-bit data maintained therein to the exclusive OR circuits 301 and 303. In synchronization with a clock signal, the shift register 304 maintains new 1-bit data supplied from the exclusive OR circuit 303 and supplies the new data to the exclusive OR circuits 301 and 303.
When the convolutional encoder 300 described above receives the 3-bit interleaved data D3011, D3012, and D3023, the convolutional encoder 300 performs a convolutional operation of the input data D3011, D3012, and D3023 and outputs the operation result as the 3-bit encoded data D3021, D3022, and D3023 to the multi-level modulation mapping circuit at the subsequent stage. In other words, the convolutional encoder 300 performs a convolutional operation to encode the inner code with a code rate of 3/3=1 and outputs the encoded data D302 to the multi-level modulation mapping circuit at the subsequent stage.
In this paper, the encoded data D3021, D3022, and D3023 generated by the convolutional encoder 300 described above are, as shown in FIG. 19, mapped by the multi-level modulation mapping circuit onto a transmission symbol in 8PSK. Referring to FIG. 19, the values of the transmission symbol assigned to each signal point indicate (D3021, D3022, D3033).
In this paper, a trellis shown in FIG. 20 is generated by encoding the inner code by the convolutional encoder 300 and assigning the encoded data to the signal points by the multi-level modulation mapping circuit. Specifically, the trellis uses S0 to represent states when the contents of the shift register 304 of the convolutional encoder 300 are zero, S1 to represent states when the contents of the shift register 304 indicate one, and (D3011, D3012, D3013)/(D3021, D3022, D3023) to represent the input/output label attached to each path. In such a case, the input/output labels 000/000, 011/010, 101/110, and 110/100 are assigned to parallel paths consisting of four paths extending from state S0 to state S0; the input/output labels 001/001, 010/011, 100/111, and 111/101 are assigned to parallel paths consisting of four paths extending from state S0 to state S1; the input/output labels 111/000, 100/010, 010/110, and 001/100 are assigned to parallel paths consisting of four paths extending from state S1 to state S0; and the input/output labels 110/001, 101/011, 011/111, and 000/101 are assigned to parallel paths consisting of four paths extending from state S1 to state S1.
A specific method for creating such a trellis that is not catastrophic will now be described.
In this paper, a trellis that is not catastrophic is created by assigning encoded data to appropriate signal points using the above-described set partitioning technique. Specifically, in this paper, eight signal points in 8PSK [0, 1, 2, 3, 4, 5, 6, 7, 8] shown in FIG. 21A are divided into two sets A=[0, 2, 4, 6] and B=[1, 3, 5, 7], as shown in FIGS. 21B and 21C, respectively. In the following description, the elements of the set A are denoted by [A0, A2, A4, A6], and the elements of the set B are denoted by [B1, B3, B5, B6]. The squared minimum distance between the signal points shown in FIG. 21A is 0.59, whereas the squared minimum distance between the signal points shown in FIGS. 21B and 21C is 2.
In the sets A and B, the signal points are assigned so that the input Hamming distance between parallel paths is two. A specific trellis is shown in FIG. 22. The input labels 000, 011, 101, and 110 are assigned to parallel paths consisting of four paths extending from state S0 to state S0; the input labels 001, 010, 100, and 111 are assigned to parallel paths consisting of four paths extending from state S0 to state S1; the input labels 111, 100, 010, and 001 are assigned to parallel paths consisting of four paths extending from state S1 to state S0; and the input labels 110, 101, 011, and 000 are assigned to parallel paths consisting of four paths extending from state S1 to state S1.
The input elements of the parallel paths consisting of four paths extending from state S1 to state S0 are the same as those of the parallel paths consisting of four paths extending from state S0 to state S1 but in a different order. The input elements of the parallel paths consisting of four paths extending from state S1 to state S1 are the same as those of the parallel paths consisting of four paths extending from state S0 to state S0 but in a different order.
In this trellis, the outputs of transitions from state S0 to state S0 and the outputs of transitions from state S1 to state S0 constitute the set A, and the outputs of transitions from state S0 to state S1 and the outputs of transitions from state S1 to state S1 constitute the set B.
The outputs of transitions from state S1 to state S0 constitute the set A and the outputs of transitions from state S1 to state S1 constitute the set B because, if the outputs of transitions from state S1 to state S0 constitute the set B, the outputs of transitions from state S1 to state S1 constitute the set A. As a result, the output of the path from state S0xe2x86x92state S0xe2x86x92state S0 becomes the same as the output of the path from state S1xe2x86x92state S1xe2x86x92state S1, resulting in a catastrophic trellis.
The input elements of transitions from state S1 to state S0 are the same as those of transitions from state S0 to state S1, and the input elements of transitions from state S1 to state S1 are the same as those of transitions from state S0 to state S0 because, if the input elements of transitions from state S1 to state S0 are the same as those of transitions from state S0 to state S0, some of the paths from state S0xe2x86x92state S0xe2x86x92state S0 and the paths from state S0xe2x86x92state S1xe2x86x92state S0 have a small output Euclidean distance with an input Hamming distance of one. When such an inner code is concatenated with the outer code via the interleaver, many codewords having a small distance are generated.
Each branch leaving state S0 of the trellis shown in FIG. 22 may have arbitrary input/output assignment among the elements of the set A or the set B. For example, as shown in FIG. 23, element A0 of the set A is assigned as the output label to the input label 000; element A2 of the set A is assigned as the output label to the input label 011; element A4 of the set A is assigned as the output label to the input label 101; and element A6 of the set A is assigned as the output label to the input label 110. At the same time, element B1 of the set B is assigned as the output label to the input label 001; element B3 of the set B is assigned as the output label to the input label 010; element B5 of the set B is assigned as the output label to the input label 100; and element B7 of the set B is assigned as the output label to the input label 111.
Each branch leaving state S1 of the trellis is determined subject to maximizing the output distance with respect to an input distance of two.
FIG. 24 shows paths with an input distance of two, on the basis of the all-zero path. Each of the elements A? shown in FIG. 24 may by one of A0, A2, A4, and A6. Thus, the sum of squares of the distances of the paths is expressed as:                     {                                                                                                  B                    1                                    +                                      A                    0                                                  =                                                      0.59                    +                    0                                    =                  0.59                                                                                                                                              B                    1                                    +                                      A                    2                                                  ,                                                      A                    6                                    =                                                            0.59                      +                      2                                        =                    2.59                                                                                                                                                                B                    1                                    +                                      A                    4                                                  =                                                      0.59                    +                    4                                    =                  4.59                                                                                                                          B                  3                                ,                                                                            B                      5                                        +                                          A                      0                                                        =                                                            3.41                      +                      0                                        =                    3.41                                                                                                                                            B                  3                                ,                                                      B                    5                                    +                                      A                    2                                                  ,                                                      A                    6                                    =                                                            3.41                      +                      2                                        =                    5.41                                                                                                                                            B                  3                                ,                                                                            B                      5                                        +                                          A                      4                                                        =                                                            3.41                      +                      4                                        =                    7.41                                                                                                          (        4        )            
One of the elements other than A0 is assigned to paths with an input distance of one, which are among the parallel paths consisting of four paths extending from state S1 to state S0, thus maximizing the output distance with respect to an input distance of two. In other words, as shown in FIG. 25, the element A0 is assigned to only one path with an input distance of three, which is one of the parallel paths consisting of four paths extending from state S1 to state S0.
Similarly, as shown in FIG. 26, the inputs corresponding to the elements A2, A4, and A6 are assigned in such a manner that, of the parallel paths consisting of four paths extending from state S0 to state S0 and the parallel paths consisting of four paths extending from state S1 to state S0, the corresponding paths between which the input distance is three have the same signal point.
The parallel paths consisting of four paths extending from state S1 to state S1 are considered using FIG. 27. Specifically, in the trellis shown in FIG. 27, of the parallel paths consisting of four paths extending from state S1 to state S1, there are only three paths with an input distance of one, that is, 000/B?, 011/B?, and 101/B?, on the basis of the path with the input label 001.
As in the case with the above discussion, of the parallel paths consisting of four paths extending from state S1 to state S1, 110 is assigned to the input of the path having the element B1 as the output, where 110 has an input distance of three on the basis of the path with the input label 001. Similarly, the inputs corresponding to the elements B3, B5, and B7 are assigned in such a manner that, of the parallel paths consisting of four paths extending from state S0 to state S1 and the parallel paths consisting of four paths extending from state S1 to state S1, the corresponding paths between which the input distance is three have the same signal point.
As a result of such operations, the input/output labels assigned to the paths in the trellis are shown in FIG. 28.
When the convolutional encoder 300 shown in FIG. 18 is used to encode the inner code, the elements A0, A2, A4, and A6 of the set A become 000, 010, 110, and 110, respectively, and the elements B1, B3, B5, and B7 of the set B become 001, 011, 111, and 101, respectively. Accordingly, a trellis that is not catastrophic, shown in FIG. 20, is created.
In an encoding device that performs mapping of the inner code to the signal points, which is described in the paper by Divsalar, et al., an output distance distribution with respect to an input distance of two is computed as follows.
Since the encoding device performs trellis coded modulation (hereinafter referred to as TCM), if the distance distributions on the basis of all paths are not the same, that is, if the trellis is not symmetrical, the average of the distance distributions need to be computed.
In the case of the above-described mapping of the inner code to the signal points, a state transition diagram on the basis of the all-zero path is shown in FIG. 29. Referring to FIG. 29, a multiplier of Y indicates an input distance and a multiplier of X indicates a squared output distance. In the state transition diagram, the paths with an input distance of two are shown in terms of a state transition diagram in FIG. 30.
An output distance distribution with respect to an input distance of two is expressed by:                                           2            ⁢                          X              2                                +                      X            4                    +                                    ∑                              n                =                0                            ∞                        ⁢                          xe2x80x83                        ⁢                                          (                                                      X                    0.59                                    +                                      2                    ⁢                                          X                      3.41                                                                      )                            ⁢                                                (                                      X                    0.59                                    )                                n                            ⁢                              (                                                      2                    ⁢                                          X                      2                                                        +                                      X                    4                                                  )                                                    =                              2            ⁢                          X              2                                +                      2            ⁢                          X              2.59                                +                      2            ⁢                          X              3.18                                +                      2            ⁢                          X              3.77                                +                      X            4                    +          ⋯                                    (        5        )            
In a state transition diagram on the basis of A2xe2x88x92A2, the paths with an input distance of two are shown in FIG. 31 in which the coefficient of the transition from state S0 to state S1 shown in FIG. 31 differs from that shown in FIG. 30.
Therefore, an output distance distribution with respect to an input distance of two is expressed by:                                           2            ⁢                          X              2                                +                      X            4                    +                                    ∑                              n                =                0                            ∞                        ⁢                          xe2x80x83                        ⁢                                          (                                                      2                    ⁢                                          X                      0.59                                                        +                                      X                    3.41                                                  )                            ⁢                                                (                                      X                    0.59                                    )                                n                            ⁢                              (                                                      2                    ⁢                                          X                      2                                                        +                                      X                    4                                                  )                                                    =                              2            ⁢                          X              2                                +                      4            ⁢                          X              2.59                                +                      4            ⁢                          X              3.18                                +                      4            ⁢                          X              3.77                                +                      X            4                    +          ⋯                                    (        6        )            
Two halves of all of the remaining paths have distance distributions expressed by equation (5) and equation (6), respectively. The average of the output distance distributions is expressed by:
2X2+3X2.59+3X3.18+3X3.77+X4+ . . . xe2x80x83xe2x80x83(7)
In the convolutional encoders 230 and 300 shown in FIGS. 16 and 18, the number of shift registers, that is, the number of memories, is one. Thus, the number of states is two. Such convolutional encoders with one memory do not terminate with an input distance of one; instead, they always terminate with an input distance of two. In other words, such convolutional encoders never terminate with an odd-numbered input distance.
In the above-described paper by Divsalar et al. in which such a convolutional encoder is used as an inner-code encoder, if the outer code has a minimum distance of three, the encoder does not terminate even with an inner code""s input distance of three, resulting in a code with a large output distance. The overall resultant code thus has a performance effectively equivalent to that of a case in which the outer code has a minimum distance of four.
On the other hand, the above paper does not discuss a case in which an encoder with two or more memories is applied to encode the inner code.
This discussion is also applicable to SCCC coding.
Accordingly, it is an object of the present invention to provide an encoding device and method for proposing, in SCCC coding and/or SCTCM coding, new guiding principles for applying an encoder with two memories to an inner code and improving the performance and to provide a decoding device and method for decoding with high accuracy a code in SCCC and/or a code in SCTCM generated by such encoding device and method.
In order to achieve the above-described objects, according to an aspect of the present invention, an encoding device that performs serially concatenated convolutional coding or serial concatenated trellis coded modulation of input data is provided. The encoding device includes a first component encoder for performing predetermined encoding of the input data; an interleaver for permuting first encoded data generated by the encoding by the first component encoder; and a second component encoder for performing predetermined encoding of interleaved data generated by the interleaver to generate second encoded data, the second component encoder being serially concatenated with the interleaver. The second component encoder includes two or more storage elements for storing data. The first encoded data generated by the first component encoder has a minimum output distance greater than the maximum input distance at which a minimum-distance code is generated by the second component encoder.
The encoding device according to the present invention uses, when an inner code is encoded by the second component encoder having two or more storage elements, an encoder, serving as the first component encoder for encoding an outer code, for generating the first encoded data having a minimum output distance greater than the maximum input distance at which a minimum-distance code is generated by the second component encoder. Accordingly, the bit error rate with a high signal-to-noise power ratio is improved, and high-performance coding is performed.
In order to achieve the above-described objects, according to another aspect of the present invention, an encoding method for performing serially concatenated convolutional coding or serial concatenated trellis coded modulation of input data is provided. The encoding method includes a first component encoding step of performing predetermined encoding of the input data; an interleaving step of permuting first encoded data generated by the encoding in the first component encoding step; and a second component encoding step of performing predetermined encoding of interleaved data generated in the interleaving step to generate second encoded data. In the second component encoding step, the encoding is performed using two or more storage elements for storing data. The first encoded data generated in the first component encoding step has a minimum output distance greater than the maximum input distance at which a minimum-distance code is generated in the second component encoding step.
The encoding method according to the present invention uses, when an inner code is encoded using two or more storage elements, an outer code that has a minimum output distance greater than the maximum input distance at which a minimum-distance inner code is generated. Accordingly, the bit error rate with a high signal-to-noise power ratio is improved, and high-performance coding is performed.
In order to achieve the above-described objects, according to yet another aspect of the present invention, a decoding device is provided that decodes a code generated by serially concatenated convolutional coding or serial concatenated trellis coded modulation by an encoding device including a first component encoder for performing predetermined encoding of input data; a first interleaver for permuting first encoded data generated by the encoding by the first component encoder; and a second component encoder for performing predetermined encoding of interleaved data generated by the first interleaver to generate second encoded data. The second component encoder is serially concatenated with the first interleaver. The second component encoder includes two or more storage elements for storing data. The first encoded data generated by the first component encoder has a minimum output distance greater than the maximum input distance at which a minimum-distance code is generated by the second component encoder. The decoding device includes a first soft-output decoder for receiving a soft-input received value and a-priori probability information corresponding to information bits, performing soft-output decoding, and generating first extrinsic information at each time, the first soft-output decoder being associated with the second component encoder; a de-interleaver for permuting the soft-input first extrinsic information generated by the first soft-output decoder so that the order of the interleaved data permuted by the first interleaver is rearranged to the order of the first encoded data generated by the encoding by the first component encoder, the de-interleaver being serially concatenated with the first soft-output decoder; a second soft-output decoder for performing soft-output decoding using soft-input a-priori probability information that is generated by the de-interleaver and that corresponds to encoded bits and soft-input a-priori probability information corresponding to the information bits and generating a-posteriori probability information and/or second extrinsic information corresponding to the information bits at each time, the second soft-output decoder being associated with the first component encoder and being serially concatenated with the de-interleaver; and a second interleaver for permuting, on the basis of the same rearrangement position information as that of the first interleaver, the soft-input second extrinsic information generated by the second soft-output decoder. The first soft-output decoder receives, as the a-priori probability information corresponding to the information bits, the soft-input second extrinsic information generated by the second interleaver.
The decoding device according to the present invention decodes, when an inner code is encoded by the second component encoder having two or more storage elements, a code that is generated using an encoder, serving as the first component encoder for encoding an outer code, for generating the first encoded data having a minimum output distance greater than the maximum input distance at which a minimum-distance code is generated by the second component encoder. Accordingly, a code having an improved bit error rate with a high signal-to-noise power ratio is decoded with high accuracy.
In order to achieve the above-described objects, according to a further aspect of the present invention, a decoding method is provided for decoding a code generated by serially concatenated convolutional coding or serial concatenated trellis coded modulation by an encoding method including a first component encoding step of performing predetermined encoding of input data; an interleaving step of permuting first encoded data generated by the encoding in the first component encoding step; and a second component encoding step of performing predetermined encoding of interleaved data generated in the interleaving step to generate second encoded data. In the second component encoding step, the encoding is performed using two or more storage elements for storing data. The first encoded data generated in the first component encoding step has a minimum output distance greater than the maximum input distance at which a minimum-distance code is generated in the second component encoding step. The decoding method includes a first soft-output decoding step of receiving a soft-input received value and a-priori probability information corresponding to information bits, performing soft-output decoding, and generating first extrinsic information at each time, the first soft-output decoding step being associated with the second component encoding step; a de-interleaving step of permuting the soft-input first extrinsic information generated in the first soft-output decoding step so that the order of the interleaved data permuted in the first interleaving step is rearranged to the order of the first encoded data generated in the encoding in the first component encoding step; a second soft-output decoding step of performing soft-output decoding using soft-input a-priori probability information that is generated in the de-interleaving step and that corresponds to encoded bits and soft-input a-priori probability information corresponding to the information bits and generating a-posteriori probability information and/or second extrinsic information corresponding to the information bits at each time, the second soft-output decoding step being associated with the first component encoding step; and a second interleaving step of permuting, on the basis of the same rearrangement position information as that of the first interleaving step, the soft-input second extrinsic information generated in the second soft-output decoding step. In the first soft-output decoding step, the soft-input second extrinsic information generated in the second interleaving step is received as the a-priori probability information corresponding to the information bits.
The decoding method according to the present invention decodes, when an inner code is encoded using two or more storage elements, an outer code that has a minimum output distance greater than the maximum input distance at which a minimum-distance inner code is generated. Accordingly, a code having an improved bit error rate with a high signal-to-noise power ratio is decoded with high accuracy.
In order to achieve the above-described objects, according to another aspect of the present invention, an encoding device that performs serially concatenated convolutional coding or serial concatenated trellis coded modulation of input data is provided. The encoding device includes a first component encoder for performing predetermined encoding of the input data; an interleaver for permuting first encoded data generated by the encoding by the first component encoder; and a second component encoder for performing predetermined encoding of interleaved data generated by the interleaver to generate second encoded data, the second component encoder being serially concatenated with the interleaver. The second component encoder includes two or more storage elements for storing data, and the second encoded data generated thereby is not terminated with an odd-numbered input distance.
The encoding device according to the present invention uses, when an inner code is encoded by the second component encoder having two or more storage elements, an encoder for generating the second encoded data that is not terminated with an odd-numbered input distance. Accordingly, the bit error rate with a high signal-to-noise power ratio is improved while the decoding cost is suppressed, and high-performance coding is performed.
In order to achieve the above-described objects, according to yet another aspect of the present invention, an encoding method for performing serially concatenated convolutional coding or serial concatenated trellis coded modulation of input data is provided. The encoding method includes a first component encoding step of performing predetermined encoding of the input data; an interleaving step of permuting first encoded data generated by the encoding in the first component encoding step; and a second component encoding step of performing predetermined encoding of interleaved data generated in the interleaving step to generate second encoded data. In the second component encoding step, two or more storage elements for storing data are used, and the second encoded data generated thereby is not terminated with an odd-numbered input distance.
The encoding method according to the present invention uses, when an inner code is encoded using two or more storage elements, a code that is not terminated with an odd-numbered input distance. Accordingly, the bit error rate with a high signal-to-noise power ratio is improved while the decoding cost is suppressed, and high-performance coding is performed.
In order to achieve the above-described objects, according to a further aspect of the present invention, a decoding device is provided that decodes a code generated by serially concatenated convolutional coding or serial concatenated trellis coded modulation by an encoding device including a first component encoder for performing predetermined encoding of input data; an interleaver for permuting first encoded data generated by the encoding by the first component encoder; and a second component encoder for performing predetermined encoding of interleaved data generated by the interleaver to generate second encoded data, the second component encoder being serially concatenated with the interleaver. The second component encoder includes two or more storage elements for storing data, and the second encoded data generated thereby is not terminated with an odd-numbered input distance. The decoding device includes a first soft-output decoder for receiving a soft-input received value and a-priori probability information corresponding to information bits, performing soft-output decoding, and generating first extrinsic information at each time, the first soft-output decoder being associated with the second component encoder; a de-interleaver for permuting the soft-input first extrinsic information generated by the first soft-output decoder so that the order of the interleaved data permuted by the first interleaver is rearranged to the order of the first encoded data generated by the encoding by the first component encoder, the de-interleaver being serially concatenated with the first soft-output decoder; a second soft-output decoder for performing soft-output decoding using soft-input a-priori probability information that is generated by the de-interleaver and that corresponds to encoded bits and soft-input a-priori probability information corresponding to the information bits and generating a-posteriori probability information and/or second extrinsic information corresponding to the information bits at each time, the second soft-output decoder being associated with the first component encoder and being serially concatenated with the de-interleaver; and a second interleaver for permuting, on the basis of the same rearrangement position information as that of the first interleaver, the soft-input second extrinsic information generated by the second soft-output decoder. The first soft-output decoder receives, as the a-priori probability information corresponding to the information bits, the soft-input second extrinsic information generated by the second interleaver.
The decoding device according to the present invention decodes, when an inner code is encoded by the second component encoder having two or more storage elements, a code that is generated using an encoder that generates the second encoded data that is not terminated with an odd-numbered input distance. Accordingly, while the decoding cost is suppressed, a code having an improved bit error rate with a high signal-to-noise power ratio is decoded with high accuracy.
In order to achieve the above-described objects, according to another aspect of the present invention, a decoding method is provided for decoding a code generated by serially concatenated convolutional coding or serial concatenated trellis coded modulation by an encoding method including a first component encoding step of performing predetermined encoding of input data; an interleaving step of permuting first encoded data generated by the encoding in the first component encoding step; and a second component encoding step of performing predetermined encoding of interleaved data generated in the interleaving step to generate second encoded data. In the second component encoding step, two or more storage elements for storing data are used, and the second encoded data generated thereby is not terminated with an odd-numbered input distance. The decoding method includes a first soft-output decoding step of receiving a soft-input received value and a-priori probability information corresponding to information bits, performing soft-output decoding, and generating first extrinsic information at each time, the first soft-output decoding step being associated with the second component encoding step; a de-interleaving step of permuting the soft-input first extrinsic information generated in the first soft-output decoding step so that the order of the interleaved data permuted in the first interleaving step is rearranged to the order of the first encoded data generated by the encoding in the first component encoding step; a second soft-output decoding step of performing soft-output decoding using soft-input a-priori probability information that is generated in the de-interleaving step and that corresponds to encoded bits and soft-input a-priori probability information corresponding to the information bits and generating a-posteriori probability information and/or second extrinsic information corresponding to the information bits at each time, the second soft-output decoding step being associated with the first component encoding step; and a second interleaving step of permuting, on the basis of the same rearrangement position information as that of the first interleaving step, the soft-input second extrinsic information generated in the second soft-output decoding step. In the first soft-output decoding step, the soft-input second extrinsic information generated in the second interleaving step is received as the a-priori probability information corresponding to the information bits.
The decoding method according to the present invention decodes, when an inner code is encoded using two or more storage elements, a code that does not terminate with an odd-numbered input distance. Accordingly, while the decoding cost is suppressed, a code having an improved bit error rate with a high signal-to-noise power ratio is decoded with high accuracy.